1. Field of the Invention
The preset invention relates to a communication network and a method thereof for realizing secrecy of data in the field of communication, in which the encryption key is changed each time communication is made, even if the other party with which communication is being made is the same party each time. More particularly, the preset invention relates to a cryptosystem for an open-algorithm common key block cipher, in which the encryption key for the block cipher is sequentially updated in order to improve safety, and to a method for updating the key for the cryptosystem.
2. Description of the Related Art
Open-algorithm common key block ciphers such as represented by the DES (Data Encryption Standard) and FEAL (Fast data Encipherment Algorithm) are defective in that the key can be analyzed in the event that a certain number or more of sets of cipher text encrypted by the key and plain text are output.
In order to deal with this defect, U.S. Pat. No. 5,600,720 (hereafter referred to as "Reference 1") proposes a cryptosystem in which the key for block cipher is periodically updated by cryptographically secure pseudo-random numbers, in which, as shown in FIG. 22, the key is updated by cryptographically secure pseudo-random numbers before outputting the number of sets of cipher text and plain text needed to analyze the key so as to complicate the difficulty in analyzing the key, thereby improving the safety of the open-algorithm common key block cipher. It must be noted here that the term "cryptographically secure pseudo-random number" refers to a pseudo-random number which is indistinguishable from a true random number by a logic circuit of a polynomial order.
In other words, a cryptographically secure pseudo-random number sequence is a number sequence in which it is extremely difficult to predict a subsequent sequence from an output sequence. Such is discussed in detail in, e.g., A. C. Yao: "Theory and Applications of Trapdoor Functions" (Proceedings of the 23rd IEEE Symposium on Foundations of Computer Science, IEEE, pp. 80-91, 1982), (hereafter referred to as "Reference 2"), and M. Blum and S. Micali: "How to Generate Cryptographically Strong Sequences of Pseudo-Random Bits" (Proc. 22nd FOCS, IEEE, pp. 112-118, 1982), (hereafter referred to as "Reference 3").
Known algorithms for generating such cryptographically secure pseudo-random numbers include such using square-type random numbers, RSA cipher, discreet logarithms, and inverse number cipher.
The cryptosystem shown in FIG. 22 is comprised of a pseudo-random number generator 1, a computing device 2, and a block encrypting device 3. The pseudo-random number generator 1 generates pseudo-random numbers following a cryptographically secure pseudo-random number algorithm. DES cipher or FEAL cipher is used as the block cipher for the algorithm for the block encrypting device 3. The key stream necessary for periodical updating of the block cipher key is obtained by dividing the cryptographically secure pseudo-random number series output from the computing device 2 into bit-lengths of the block cipher key. The block cipher key is updated by means of sequentially using the key stream k1, k2, . . . , as the block cipher key. The block encrypting device 3 performs encrypting of the plain text block stream 5 (communication text: M.sub.11 to M.sub.1s, M.sub.21 to M.sub.2s, . . . , M.sub.t1 to M.sub.ts) into the cipher block stream 6 (k.sub.1 (M.sub.11)) to k.sub.1 (M.sub.1s), k.sub.2 (M.sub.21) to k.sub.2 (M.sub.2s), . . . , k.sub.t (M.sub.t1) to k.sub.t (M.sub.ts)), and deciphering of the cipher text.
The pseudo-random number generator 1 which generates cryptographically secure pseudo-random numbers due to algorithms using square-type random numbers, RSA cipher, discreet logarithms, and inverse number cipher, is configured as shown in FIG. 23. The operation thereof is as shown below:
(1) x.sub.0 =K.sub.AB is input into the pseudo-random number generator 1 as the initial value 4.
(2) x.sub.1, x.sub.2, . . . , is generated by feedback calculation x.sub.i+1 =f (x.sub.i) (i=0, 1, . . . ) in the first computing unit 101.
(3) In the second computing unit 102, calculation b.sub.i+1 =g (x.sub.i+1) (i=0, 1, . . . ) is performed from the generated x.sub.1, x.sub.2, . . . , and the obtained b.sub.1, b.sub.2, . . . , b.sub.m is output as pseudo-random number 7 (CR.sub.AB).
In the above procedures, x.sub.i+1 which is periodically updated by feedback calculation is referred to as an internal variable within the pseudo-random number generator 1. Also, the procedures necessary to generate a pseudo-random number b.sub.1 obtained at one time is referred to as one step.
Further, the computing device 2 converts the output CR.sub.AB obtained from the pseudo-random number generator 1 into the block cipher key stream k.sub.1, k.sub.2, . . . , k.sub.t. Each of the keys k.sub.u (u=1, 2, . . . , t) of the block cipher are bit streams of a certain length which is determined by the algorithm of the block cipher used, and are generated by the computing device 2 dividing the cryptographically secure pseudo-random number stream CR.sub.AB in the determined bit lengths.
In FIG. 22, M.sub.uv (u=1, 2, . . . , t:v=1, 2, . . . , s) represents plain text block 5, k.sub.u (u=1, 2, . . . , t) represents the key stream 8 of the block cipher, k.sub.u (M.sub.uv) (u=1, 2, . . . , t:v=1, 2, . . . , s) represents the cipher text block stream 6 obtained by encrypting the plain text M.sub.uv with the encryption key k.sub.u. Here, the number s blocks from M.sub.u1 to M.sub.us is encrypted using the same key k.sub.u. The plain text block 5 shown in FIG. 22 is encrypted by a plurality of encrypting keys by means of sequentially using the aforementioned pseudo-random number stream as the block cipher key.
According to this cryptosystem, the number of plain text block encrypted by the same key is s, so analyzing of the key can be made difficult in the event that the number of sets of plain text blocks and cipher text blocks necessary for analysis of the key exceeds the number s.
In other words, the shorter the cycle for updating the block cipher key is, the further the number of pieces of plain text encrypted with the same key is reduced, thereby improving the safety thereof.
However, with the arrangement described in Reference 1, the aforementioned cryptographically secure pseudo-random number stream 7 (CR.sub.AB) is divided into bit lengths of the block cipher key and used sequentially as the block cipher key, so once a key is updated, updating to the next key cannot be made until pseudo-random numbers in bit lengths of the block cipher key are output anew from the pseudo-random number generator 1.
Now, this will be quantitatively evaluated. The updating cycle of the block cipher key can be calculated as follows. In the event that cryptographically secure pseudo-random numbers generated at the speed of w.sub.r (bps) are used in a situation wherein, as shown in FIG. 24, the bit length of each block to be encrypted at one time is m.sub.b (bits), the bit length of the encryption key is m.sub.k (bits), and the encryption processing speed is w.sub.e (bps), the number of block encryption keys w.sub.k generated per second can be calculated as follows: EQU w.sub.k =w.sub.r /m.sub.k.
The number of blocks w.sub.b which can be encrypted per second is: EQU w.sub.b =w.sub.e /m.sub.b,
and accordingly, the number of blocks s encrypted with one encryption key is: EQU s=w.sub.b /w.sub.k.
The number of plain text blocks s encrypted with the same encryption key can be thus obtained.
For example, let us calculated what s will be under the following &lt;Conditions 1&gt;.
&lt;Conditions 1&gt;
(Block encryption)
Bit length of blocks encrypted at one time: 64 bits (m.sub.b =64) PA1 Bit length of encryption key: 72 bits (m.sub.k =72) PA1 Encryption processing speed: 128 Mbps (w.sub.e =128.times.10.sup.6) (generation of pseudo-random numbers) PA1 Number of pseudo-random numbers b.sub.i output at one time: 9 bits PA1 Processing time per step: 10.sup.-3 seconds
Now, the processing time per step refers to the processing time necessary to obtain a single b.sub.i. That is, in the case of &lt;Conditions 1&gt;, a 9-bit pseudo-random number can be obtained every 10.sup.-3 seconds. Accordingly, the pseudo-random number generating speed w.sub.r is: EQU w.sub.r =9.times.10.sup.3 (bps).
Calculating the number of block encryption keys w.sub.k generated per second, the following holds. EQU w.sub.k =w.sub.r /m.sub.k =2.sup.-3.times.10.sup.3
The number of blocks w.sub.b which can be encrypted per second is: EQU w.sub.b =w.sub.e /m.sub.b =2.times.10.sup.6,
so the number of blocks s encrypted by one encryption key is: EQU s=w.sub.b /w.sub.k =2.sup.4.times.10.sup.3.
That is to say, in the event that updating of block encryption keys is performed according to Reference 1 under &lt;Conditions 1&gt;, the key is updated each time 2.sup.4.times.10.sup.3 blocks are encrypted.
FIG. 25 schematically shows the processing performed in the case that block cipher key updating is carried out according to Reference 1 under &lt;Conditions 1&gt;. As shown in the Figure, a 9-bit pseudo-random number can be obtained with one step of the pseudo-random number generating device 1, so eight steps are required for generating a 72-bit block cipher key. Hence, the first block cipher key k.sub.1 is: EQU k.sub.1 =b.sub.1, b.sub.2, b.sub.3, b.sub.4, b.sub.5, b.sub.6, b.sub.7, b.sub.8,
and the first 2.sup.4.times.10.sup.3 blocks of the plain text block stream 5 are encrypted with this key.
Further, the next block cipher key k.sub.2 is obtained by the subsequent eight steps of the pseudo-random number generating device 1, yielding: EQU k.sub.2 =b.sub.9, b.sub.10, b.sub.11, b.sub.12, b.sub.13, b.sub.14, b.sub.15, b.sub.16.
The second 2.sup.4.times.10.sup.3 blocks of the plain text block stream 5 are encrypted with this key by the block encrypting device 3.
In this case, the computing device 2 gathers the pseudo-random numbers 7 (b.sub.1, b.sub.2, . . . , b.sub.8, b.sub.9, b.sub.10, . . . ) input from the pseudo-random number generating device, eight at a time, arrays these sequentially in the order of input, and outputs the result as the block cipher key stream 8 (k.sub.1, k.sub.2, . . . ).
As can be seen from the above, in the case of attempting to periodically update the block keys according to the method described in Reference 1 using cryptographically secure pseudo-random numbers, only one key update can be performed each time pseudo-random numbers equal to the bit length of the block cipher key is output from the pseudo-random number generating device 1.
Also, with an encrypted communication network, unique keys are appropriated to all pairs of network subscribers beforehand, and the two subscribers hold the unique key in secret. Sharing of the key can be realized either by the network administrator or the like setting the key, or by a known key sharing method. Further, each subscriber has a communication terminal comprising; an encryption device 3 for performing encryption (deciphering) following an algorithm stipulated on the network, as shown in FIG. 22; a pseudo-random number generator 1 for generating cryptographically secure pseudo-random numbers following an algorithm stipulated on the network; and a computing device 2 for converting the pseudo-random numbers output from the pseudo-random number generator 1 into a key stream.
The encrypted communication from subscriber A to B using this communication terminal is performed according to the following procedures, for example.
(1) The sender A sets the secret key K.sub.AB which has been distributed beforehand and is shared with the destination B at the initial value X.sub.0 of the pseudo-random number generator 1 and operates the pseudo-random number generator 1, thereby generating cryptographically secure pseudo-random number stream 7 (CR.sub.AB). Further, the CR.sub.AB generated thereby is converted into a block cipher key stream 8 (k.sub.1, k.sub.2, . . . , k.sub.t). These are used while periodically updating as block cipher keys, thereby encrypting the plain text block stream 5 (communication text M.sub.uv ; u=1, 2, . . . , t:v=1, 2, . . . , s) with the block encryption device 3, and the encrypted cipher text block stream 6 (k.sub.u (M.sub.uv); u=1, 2, . . . , t:v=1, 2, . . . , s) is sent to the destination B.
(2) The destination B sets the secret key K.sub.AB which has been distributed beforehand and is shared with the destination A at the initial value X.sub.0 of the pseudo-random number generator 1 and operates the pseudo-random number generator 1, thereby generating cryptographically secure pseudo-random number stream 7 (CR.sub.AB). Further, the CR.sub.AB generated thereby is converted into a block cipher key stream 8 (k.sub.1, k.sub.2, . . . , k.sub.t). These are used while periodically updating as block cipher keys, thereby obtaining the received cipher text block stream 6 (k.sub.u (M.sub.uv); u=1, 2, . . . , t:v 1, 2, . . . , s) sent from the sender A by using the block encryption device 3.
However, according to this method, in the event that communication between the subscribers is ended and then restarted, the initial value of the pseudo-random number generator 1 is reset to the key K.sub.AB which has already been used earlier, which is problematic in that secrecy cannot be sufficiently maintained.
Also, there is a known method for using a different cipher key per instance of communication, called a session key, but this session key is discarded each time communication is made, so while generating a session key is simple, the generation thereof has been based on pseudo-random numbers not cryptographically secure.
Also, a method is known in which a new secret key K'.sub.AB is communicated at the end of each communication to serve as the next initial value, thereby updating the mutually shared key, but there has been the problem in that the amount of communication increases due to updating the key.
Also, there has been the problem in the event that block cipher keys are to be updated with known methods using cryptographically secure pseudo-random numbers, in that only one key update can be performed each time pseudo-random numbers equal to the bit length of the block cipher key are output.